import { useState, useMemo } from 'react';
import { TreeNode, buildBSTFromArray, lowestCommonAncestorBST } from '@ds/tree';
import { Space, Input, Select, Typography, Alert, Card } from 'antd';
import type { SelectProps } from 'antd';
import type { ReactNode } from 'react';

const { Title, Text } = Typography;

interface NodeProps {
  node: TreeNode;
  isP?: boolean | null;
  isQ?: boolean | null;
  isLCA?: boolean | null;
  onNodeClick?: (node: TreeNode) => void;
}

/**
 * 查找树中值为target的节点
 */
function findNode(root: TreeNode | null, target: number): TreeNode | null {
  if (!root) return null;
  if (root.val === target) return root;
  return findNode(root.left, target) || findNode(root.right, target);
}

/**
 * 生成树的层次结构
 */
function levelOrder(root: TreeNode | null): (TreeNode | null)[][] {
  const result: (TreeNode | null)[][] = [];
  if (!root) return result;

  const queue: (TreeNode | null)[] = [root];
  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel: (TreeNode | null)[] = [];
    let hasNonNull = false;

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node || null);

      if (node) {
        hasNonNull = true;
        queue.push(node.left);
        queue.push(node.right);
      } else {
        queue.push(null);
        queue.push(null);
      }
    }

    if (hasNonNull) {
      result.push(currentLevel);
    } else {
      break;
    }
  }

  return result;
}

/**
 * 渲染单个节点
 */
function TreeNodeComponent({ node, isP, isQ, isLCA, onNodeClick }: NodeProps): ReactNode {
  if (!node) return null;

  // 确定节点样式
  let backgroundColor = '#fff';

  // 使用与BinaryTreeLCA组件相同的颜色方案
  if (isLCA) backgroundColor = '#ffe58f';
  if (isP || isQ) backgroundColor = '#b7eb8f';
  if ((isP || isQ) && isLCA) backgroundColor = '#fadb14';

  return (
    <div
      onClick={() => onNodeClick?.(node)}
      style={{
        minWidth: 36,
        minHeight: 36,
        border: '1px solid #aaa',
        borderRadius: 18,
        display: 'flex',
        alignItems: 'center',
        justifyContent: 'center',
        margin: '0 5px',
        background: backgroundColor,
        cursor: 'pointer',
      }}
      title={(isLCA ? 'LCA ' : '') + (isP ? '节点p ' : '') + (isQ ? '节点q' : '')}
    >
      {node.val}
    </div>
  );
}

/**
 * 二叉搜索树的最近公共祖先可视化组件
 */
export default function BSTLowestCommonAncestor() {
  const [input, setInput] = useState('6,2,8,0,4,7,9,null,null,3,5');
  const [pValue, setPValue] = useState<number | null>(null);
  const [qValue, setQValue] = useState<number | null>(null);

  // 解析输入数组
  const values = useMemo(
    () =>
      input
        .split(/[\,\s]+/)
        .filter(Boolean)
        .map((v) => (v === 'null' ? null : Number(v)))
        .filter((n) => n === null || Number.isFinite(n)),
    [input]
  );

  // 构建二叉搜索树
  const root = useMemo(() => {
    const validValues = values.filter((v) => v !== null) as number[];
    return buildBSTFromArray(validValues);
  }, [values]);

  // 获取LCA
  const lca = useMemo(() => {
    if (!root || pValue === null || qValue === null) return null;

    const pNode = findNode(root, pValue as number);
    const qNode = findNode(root, qValue as number);

    if (!pNode || !qNode) return null;

    return lowestCommonAncestorBST(root, pNode, qNode);
  }, [root, pValue, qValue]);

  // 获取树中所有节点的值作为选择选项
  const allValues = useMemo(() => {
    const result: number[] = [];

    function traverse(node: TreeNode | null) {
      if (!node) return;
      result.push(node.val);
      traverse(node.left);
      traverse(node.right);
    }

    traverse(root);
    return Array.from(new Set(result)).sort((a, b) => a - b);
  }, [root]);

  // 获取树的层次结构用于渲染
  const treeLevels = useMemo(() => levelOrder(root), [root]);

  // 处理节点点击事件
  const handleNodeClick = (node: TreeNode) => {
    // 如果pValue未设置，设置为pValue
    if (pValue === null) {
      setPValue(node.val);
    }
    // 如果qValue未设置且点击的不是pValue，设置为qValue
    else if (qValue === null && node.val !== pValue) {
      setQValue(node.val);
    }
    // 否则重置选择，设置为pValue
    else {
      setPValue(node.val);
      setQValue(null);
    }
  };

  // 选择选项
  const options: SelectProps['options'] = allValues.map((val) => ({
    label: String(val),
    value: val,
    disabled: (pValue !== null && val === pValue) || (qValue !== null && val === qValue),
  }));

  return (
    <Space direction="vertical" size="middle" style={{ width: '100%' }}>
      <Title level={2}>LeetCode 235. 二叉搜索树的最近公共祖先</Title>

      <Alert
        message="题目说明"
        description={
          <Typography.Paragraph style={{ marginBottom: 0 }}>
            给定一个二叉搜索树，找到该树中两个指定节点的最近公共祖先。
            <br />
            利用二叉搜索树的特性：左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值。
            <Typography.Link
              href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/"
              target="_blank"
              style={{ marginLeft: 8 }}
            >
              题目链接
            </Typography.Link>
          </Typography.Paragraph>
        }
        type="info"
        showIcon
      />

      <Space>
        <Input
          placeholder="输入二叉树节点值（用逗号分隔，例如：6,2,8,0,4,7,9,null,null,3,5）"
          value={input}
          onChange={(e) => {
            setInput(e.target.value);
            setPValue(null);
            setQValue(null);
          }}
          style={{ width: 400 }}
        />

        <Select
          placeholder="选择节点 p"
          style={{ width: 120 }}
          value={pValue}
          onChange={(value) => {
            setPValue(value);
            // 如果选择的p值与q值相同，重置q值
            if (value === qValue) {
              setQValue(null);
            }
          }}
          options={options}
        />

        <Select
          placeholder="选择节点 q"
          style={{ width: 120 }}
          value={qValue}
          onChange={(value) => {
            // 确保p和q是不同的节点
            if (value !== pValue) {
              setQValue(value);
            }
          }}
          options={options}
        />
      </Space>

      {pValue !== null && qValue !== null && (
        <Alert
          message={`最近公共祖先: ${lca ? lca.val : '未找到有效节点'}`}
          type={lca ? 'success' : 'warning'}
          showIcon
        />
      )}

      <Card title="二叉搜索树可视化" style={{ width: '100%', minHeight: 300 }}>
        <Text type="secondary">提示：点击树中的节点可快速选择 p 和 q</Text>
        {treeLevels.length > 0 ? (
          <div style={{ display: 'flex', justifyContent: 'center', marginTop: 10 }}>
            <div>
              {treeLevels.map((level, levelIndex) => (
                <div
                  key={levelIndex}
                  style={{
                    display: 'flex',
                    justifyContent: 'center',
                    marginBottom: 20,
                  }}
                >
                  {level.map((node, nodeIndex) => {
                    if (!node) {
                      return (
                        <div
                          key={`${levelIndex}-${nodeIndex}`}
                          style={{
                            minWidth: 36,
                            minHeight: 36,
                            margin: '0 5px',
                          }}
                        >
                          <span style={{ color: '#ccc' }}>null</span>
                        </div>
                      );
                    }

                    return (
                      <TreeNodeComponent
                        key={`${levelIndex}-${nodeIndex}`}
                        node={node}
                        isP={node.val === pValue}
                        isQ={node.val === qValue}
                        isLCA={lca && node.val === lca.val}
                        onNodeClick={handleNodeClick}
                      />
                    );
                  })}
                </div>
              ))}
            </div>
          </div>
        ) : (
          <Typography.Text
            type="secondary"
            style={{ textAlign: 'center', display: 'block', marginTop: 20 }}
          >
            请输入有效的树节点数据
          </Typography.Text>
        )}
      </Card>

      <div style={{ marginTop: 20, padding: 15, backgroundColor: '#f5f5f5', borderRadius: 5 }}>
        <Title level={4}>算法说明</Title>
        <Typography.Paragraph>
          二叉搜索树的最近公共祖先算法利用了BST的性质，可以高效地找到LCA：
        </Typography.Paragraph>
        <ol>
          <li>如果p和q的值都小于根节点的值，LCA一定在左子树中</li>
          <li>如果p和q的值都大于根节点的值，LCA一定在右子树中</li>
          <li>如果一个在左子树，一个在右子树，或者其中一个就是根节点，那么根节点就是LCA</li>
        </ol>
        <Typography.Text type="secondary">
          时间复杂度：O(h)，空间复杂度：O(h)，其中h是树的高度。
        </Typography.Text>
      </div>

      <Typography.Text type="secondary">
        注：输入格式为层序遍历的节点值，null表示空节点。选中的节点p和q会以绿色高亮显示，最近公共祖先以黄色高亮显示，既是LCA又是p或q的节点以亮黄色显示。
      </Typography.Text>
    </Space>
  );
}
